1. Technical Field
The present disclosure relates to a method for performing a histogram using an array of addressable registers.
2. Description of Related Art
Radix-based sorting algorithms sort according to integer representations or keys which are multidigit numbers in which each digit is an integer with a value in the range <0 . . . (m−1)> where m is the radix. A 32-bit integer, for example, could be treated as a 4 digit number with radix 232/4=28=256. The radix m is usually chosen to minimize the running time and is highly dependent on the implementation and the number of keys being sorted. Most digital computers internally represent all of their data as electronic representations of binary numbers, so processing the digits of integer representations by groups of binary digit representations is most convenient. Two classifications of radix sorts include least significant digit (LSD) radix sorts and most significant digit (MSD) radix sorts. LSD radix sorts process the integer representations starting from the least significant digit and move towards the most significant digit. MSD radix sorts process the integer representations starting from the most significant digit and moves towards the least significant digit.
The Sobel operator, as may be used in image processing for edge detection, calculates the gradient of the image intensity, e.g. grayscale or color at each point, and provides the direction of the largest change in intensity and the rate of change in that direction. The intensity gradient indicates how “abruptly” or “smoothly” the image intensity changes at a point of the image, and how likely it is that the point of the image represents an edge. At each point in the image, the result of the Sobel operator may include either the gradient, or the normal of the gradient. The Sobel operator is based on convolving the image with a small integer valued filter in horizontal and vertical direction.
The Hough Transform is well known in the area of computer vision for use in a method for detecting contours or shapes in images. Using this method, a Hough transform image is created from a source image. An intensity gradient, at every point in the source image may be determined in different ways, one example being use of the Sobel operator. The Hough transform image is defined such that every point in the Hough transform image represents a line or curve in the source image. The intensity of a spot in the Hough transform image is determined by the number of points of an edge on the line in the source image along with the position and intensity gradient of the edge. The intensity of the spot in Hough transform space represents the significance or weight of the line in the source image and is determined by performing a histogram, summing the weights over distances and/or angles in the source image.
In general, calculation of a histogram, e.g. the Hough Transform algorithm when implemented in a computer system generally requires a large number of random access read and write operations over a large address space. Histogram algorithms are expensive in terms of execution time due to the number of cache misses of random access operations.
Thus there is a need for and it would be advantageous to have a more efficient system and method for accelerating histogram calculations, for instance the Hough Transform algorithm for detection of shapes and contours in images.